//#include <iostream>
//#include <vector>
//#include <deque>
//#include <limits>
//
//using namespace std;
//
//// 使用SPFA算法计算最短路径
//vector<int> spfa(const vector<vector<int>>& graph, int n, int s) {
//	// 初始化距离数组，初始化为最大值表示无穷大
//	vector<int> dist(n + 1, numeric_limits<int>::max());
//	dist[s] = 0;
//	
//	// 使用双端队列实现SPFA算法中的队列
//	deque<int> queue;
//	queue.push_back(s);
//	
//	// 记录节点是否在队列中
//	vector<bool> inQueue(n + 1, false);
//	inQueue[s] = true;
//	
//	// SPFA算法主循环
//	while (!queue.empty()) {
//		int u = queue.front();
//		queue.pop_front();
//		inQueue[u] = false;
//		
//		// 遍历从节点u出发可以到达的所有节点v
//		for (int v = 1; v <= n; v++) {
//			// 如果存在从u到v的边，则尝试更新最短距离
//			if (graph[u][v] != numeric_limits<int>::max() && dist[u] + graph[u][v] < dist[v]) {
//				dist[v] = dist[u] + graph[u][v];
//				// 如果v不在队列中，则加入队列
//				if (!inQueue[v]) {
//					queue.push_back(v);
//					inQueue[v] = true;
//				}
//			}
//		}
//	}
//	
//	// 返回从起点s到各个节点的最短距离
//	return vector<int>(dist.begin() + 1, dist.end());
//}
//
//int main() {
//	int n, m, s;
//	cin >> n >> m >> s;
//	
//	// 建立邻接矩阵表示图，初始距离为无穷大
//	vector<vector<int>> graph(n + 1, vector<int>(n + 1, numeric_limits<int>::max()));
//	for (int i = 0; i < m; i++) {
//		int u, v, w;
//		cin >> u >> v >> w;
//		// 如果存在多条边，则选取最小的权值进行更新
//		graph[u][v] = min(graph[u][v], w);
//	}
//	
//	// 计算从起点s到各个节点的最短距离
//	vector<int> dist = spfa(graph, n, s);
//	
//	// 输出各个节点的最短距离
//	for (int i = 0; i < dist.size(); i++) {
//		cout << dist[i] << " ";
//	}
//	cout << endl;
//	
//	return 0;
//}
#include<bits/stdc++.h>
using namespace std;

#define INF 1e9
const int N=5e3+1;
typedef long long ll;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

struct node {
	int dis,id;
	inline bool operator < (const node &x) const {
		return dis>x.dis;
	} node (int x,int y) {dis=x,id=y;}
} ; bool vis[N];
int n,m,in[N];
ll h[N],dis[N];
vector<pair<int,int> > G[N];

inline bool SPFA(int s) { //从源点开始求一遍最短路 , 记为 h
	queue<int>q; memset(h,0x3f,sizeof(h));
	h[s]=0; vis[s]=1; q.push(s);
	while(!q.empty()) {
		int u=q.front(); q.pop(); vis[u]=0;
		for(int i=0;i<G[u].size();i++) {
			int v=G[u][i].first,w=G[u][i].second;
			if(h[v]>h[u]+w) {
				h[v]=h[u]+w;
				if(!vis[v]) {
					vis[v]=1; q.push(v);
					if(++in[v]>=n) return 0;
				}
			}
		}
	} return 1;
}

inline void dijkstra(int s) { //从每个点开始走一遍最短路模板
	priority_queue<node> q; memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++) dis[i]=(i==s)?0:(INF);
	q.push(node(0,s)); while(!q.empty()) {
		int u=q.top().id; q.pop(); if(vis[u]) continue;
		vis[u]=1; for(int i=0;i<G[u].size();i++) {
			int v=G[u][i].first,w=G[u][i].second;
			if(dis[v]>dis[u]+w) {
				dis[v]=dis[u]+w;
				if(!vis[v]) q.push(node(dis[v],v));
			}
		}
	}
}

int main(){
	n=read(),m=read();
	while(m--) {
		int u=read(),v=read(),w=read();
		G[u].push_back(make_pair(v,w));
		//		G[v].push_back(make_pair(u,w));
	} for(int i=1;i<=n;i++) G[0].push_back(make_pair(i,0)); //创造上帝视角
	if(!SPFA(0)) {puts("-1");return 0;} //负环结束
	for(int u=1;u<=n;u++)
		for(int i=0;i<G[u].size();i++) 
			G[u][i].second+=h[u]-h[G[u][i].first]; //重构
	for(int i=1;i<=n;i++) {
		dijkstra(i); ll ans=0;
		for(int j=1;j<=n;j++)
			ans+=(dis[j]==INF)?(j*INF):(j*(dis[j]+h[j]-h[i]));
		printf("%lld\n",ans);	//跑最短路并统计答案
	}	
	return 0;
}
